package main

import "fmt"

type TreeNode struct {
	val int
	lchild *TreeNode
	rchild *TreeNode
}
//递归创建二叉树
//nums数组逐层存放树的结点值，i初始值为0
func creTree(nums []int, i int)*TreeNode{
	if i > len(nums) || nums[i] == -1{
		return nil
	}
	t := &TreeNode{val: nums[i]}
	if 2*i+1 < len(nums){
		t.lchild = creTree(nums, 2*i+1)
	}
	if 2*i+2 < len(nums){
		t.rchild = creTree(nums, 2*i+2)
	}
	return t
}

func findIndex(arr []int, val int) int {
	for i := 0; i < len(arr); i++ {
		if arr[i] == val {
			return i
		}
	}
	return -1
}
//查找某一值在树中的结点位置
func (t *TreeNode)findNode(a int)*TreeNode{
	if t != nil{
		if t.val == a{
			return t
		}
		l := t.lchild.findNode(a)
		r := t.rchild.findNode(a)
		if l != nil{
			return l
		} else {
			return r
		}
	}else{
		return nil
	}
}
func (t *TreeNode)find_comm(nums []int, a *TreeNode, b *TreeNode)int{
	if a.rchild != nil || a.lchild != nil || b.rchild != nil ||b.lchild != nil{
		return -1
	}
	var i, j int
	i = findIndex(nums, a.val)
	j = findIndex(nums, b.val)
	if i == -1 || j == -1{
		return -1
	}
	for i != j{
		if i < j{
			if j%2 == 0{
				j = (j-2)/2
			}else{
				j = (j-1)/2
			}
		}else {
			if i%2 == 0{
				i = (i-2)/2
			}else{
				i = (i-1)/2
			}
		}
		//fmt.Println(i, j)
	}
	//返回下标值
	return i
}
func main(){
	nums := []int{1, 2, 3, 4, 5, 6, 7, -1, 9}
	T := creTree(nums, 0)
	fmt.Println(nums)
	fmt.Println("输入要查找的两结点：")
	var a, b int
	fmt.Scan(&a, &b)
	c := T.find_comm(nums, T.findNode(a), T.findNode(b))
	if c == -1{
		fmt.Println("输入错误，没有这个结点或者不是叶子结点")
	}else {
		fmt.Println("公共结点为：", nums[c])
	}
}